package leetcode.code;

/**
 * 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
 *
 * 示例:
 *
 * 输入:
 *
 * 1 0 1 0 0
 * 1 0 1 1 1
 * 1 1 1 1 1
 * 1 0 0 1 0
 *
 * 输出: 4
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximal-square
 */
public class 最大正方形 {

    public static int maximalSquare(char[][] matrix) {
        if (matrix.length == 0) return 0;
        int m = matrix.length;
        int n = matrix[0].length;
        int max = matrix[0][0]=='1' ? 1 : 0;
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                max = Math.max(max, max(matrix, i, j, m, n));
            }
        }
        return max;
    }

    private static int max(char[][] matrix, int x, int y, int m, int n){
        if (matrix[x][y] == '0') return 0;
        int tmp = 1;
        for (int i = 1; x+i<m && y+i<n; i++){
            for (int j = x; j <= x+i; j++){
                if (matrix[j][y+i] != '1') return tmp;
            }
            for (int j = y; j <= y+i; j++){
                if (matrix[x+i][j] != '1') return tmp;
            }
            tmp = (i+1)*(i+1);
        }
        return tmp;
    }

    public static void main(String[] args){
        char[][] a = new char[][]{{'0', '0', '0', '0', '0', '0', '0', '1'},{'0', '0', '0', '0', '0', '0', '0', '1'},
                {'0', '0', '0', '0', '0', '0', '0', '0'},{'0', '0', '1', '1', '0', '0', '0', '0'},{'0', '1', '1', '0', '0', '0', '0', '0'}};
        System.out.println(maximalSquare(a));
    }
}
